# 55/100 回溯-全排列
# leetcode第46题: https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/30

"""回溯法
回溯法主要解决的问题:
1. 组合问题
例如: 在数组nums中, 找出两数之和大于等于n的所有组合. 对于nums=[1,2,3,4],n=4, 答案为 [1,3] [1,4] [2,3] [2,4] [3,4] 共5个组合
2. 切割问题
例如: 请找出给定字符串s中所有回文子串. 对于s="ababa", 回文子串有[a,b,a] [b,a,b] [a,b,a] [a,b,a,b,a] 4种
3. 子集问题
例如: 找出nums中的所有子集
4. 排列问题
对比"组合问题"来说, 排列问题强调顺序, 而组合问题一般不强调顺序性.
在组合问题中的例子来说, 在数组nums中, 找出两数之和大于等于n的所有"排列".
[1,3] [3,1] [1,4] [4,1] [2,3] [3,2] [2,4] [4,2] [3,4] [4,3]  共10种排列方式
5. 棋盘问题
经典的"N皇后","解数独"等

一般来说回溯法使用一个递归的过程, 是一种纯粹的暴力搜索.
回溯法的递归过程可以抽象为一个树形结构, 一般来说是一个n叉树结构, n为每个决策点可选的分支数量, 而整个树的宽度就是回溯法需要处理的集合的大小,
树的深度就是递归的深度.
以下为回溯法常用的递归函数的模板:
def backtracking(params): -> None:
    if ending_condition(终止条件):
        collect result  # 收集结果
        return result  #返回结果
    for item in items:  # 遍历元素集合中的每个元素
        handle node  # 处理节点
        backtracking(params)  # 递归过程
        back tracking  # 回溯操作

实际上, 回溯算法可以类比于使用dfs算法遍历一个树形结构:
上面代码中的终止条件就是遍历到叶子节点的情况;
遍历元素部分就是遍历每个节点的所有子节点

def dfs(depth):
    if depth==n:
        print(path)
        return
    for i in range(1,n+1):
        if vis[i]:
            continue
        vis[i]=1
        path.append(i)
        dfs(depth+1)
        path.pop(-1)


"""
from leetcode import test
from itertools import permutations


def permute(nums: list[int]) -> list[list[int]]:
    def backtracking(path, used):
        if len(path) == len(nums):  # 终止条件
            res.append(path[:])  # 收集结果
            return
        for i, num in enumerate(nums):
            if used[i]:
                continue
            path.append(num)
            used[i] = True
            backtracking(path, used)  # 递归过程
            path.pop()  # 回溯操作
            used[i] = False

    res = []
    backtracking([], [False for _ in range(len(nums))])
    return res


def permute_library(nums: list[int]) -> list[list[int]]:
    return list(permutations(nums))


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3]}, {"nums": [0, 1]}, {"nums": [1]}, ]

    out = [[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]],
           [[0, 1], [1, 0]], [[1]]]

    test.test_function(permute, inp, out)
    test.test_function(permute_library, inp, out)
